home *** CD-ROM | disk | FTP | other *** search
/ PsL Monthly 1993 December / PSL Monthly Shareware CD-ROM (December 1993).iso / prgmming / dos / c / snippet.exe / LZHUF.C < prev    next >
C/C++ Source or Header  |  1990-05-04  |  19KB  |  647 lines
  1. /**************************************************************
  2.     lzhuf.c
  3.     written by Haruyasu Yoshizaki 1988/11/20
  4.     some minor changes 1989/04/06
  5.     comments translated by Haruhiko Okumura 1989/04/07
  6.     getbit and getbyte modified 1990/03/23 by Paul Edwards
  7.       so that they would work on machines where integers are
  8.       not necessarily 16 bits (although ANSI guarantees a
  9.       minimum of 16).  This program has compiled and run with
  10.       no errors under Turbo C 2.0, Power C, and SAS/C 4.5
  11.       (running on an IBM mainframe under MVS/XA 2.2).  Could
  12.       people please use YYYY/MM/DD date format so that everyone
  13.       in the world can know what format the date is in?
  14.     external storage of filesize changed 1990/04/18 by Paul Edwards to
  15.       Intel's "little endian" rather than a machine-dependant style so
  16.       that files produced on one machine with lzhuf can be decoded on
  17.       any other.  "little endian" style was chosen since lzhuf
  18.       originated on PC's, and therefore they should dictate the
  19.       standard.
  20.     initialization of something predicting spaces changed 1990/04/22 by
  21.       Paul Edwards so that when the compressed file is taken somewhere
  22.       else, it will decode properly, without changing ascii spaces to
  23.       ebcdic spaces.  This was done by changing the ' ' (space literal)
  24.       to 0x20 (which is the far most likely character to occur, if you
  25.       don't know what environment it will be running on.
  26. **************************************************************/
  27. #include <stdio.h>
  28. #include <stdlib.h>
  29. #include <string.h>
  30. #include <ctype.h>
  31.  
  32. FILE  *infile, *outfile;
  33. static unsigned long int  textsize = 0, codesize = 0, printcount = 0;
  34.  
  35. char wterr[] = "Can't write.";
  36.  
  37. static void Error(char *message)
  38. {
  39.     printf("\n%s\n", message);
  40.     exit(EXIT_FAILURE);
  41. }
  42.  
  43. /********** LZSS compression **********/
  44.  
  45. #define N       4096    /* buffer size */
  46. #define F       60  /* lookahead buffer size */
  47. #define THRESHOLD   2
  48. #define NIL     N   /* leaf of tree */
  49.  
  50. unsigned char
  51.         text_buf[N + F - 1];
  52. static int     match_position, match_length,
  53.         lson[N + 1], rson[N + 257], dad[N + 1];
  54.  
  55. static void InitTree(void)  /* initialize trees */
  56. {
  57.     int  i;
  58.  
  59.     for (i = N + 1; i <= N + 256; i++)
  60.         rson[i] = NIL;        /* root */
  61.     for (i = 0; i < N; i++)
  62.         dad[i] = NIL;         /* node */
  63. }
  64.  
  65. static void InsertNode(int r)  /* insert to tree */
  66. {
  67.     int  i, p, cmp;
  68.     unsigned char  *key;
  69.     unsigned c;
  70.  
  71.     cmp = 1;
  72.     key = &text_buf[r];
  73.     p = N + 1 + key[0];
  74.     rson[r] = lson[r] = NIL;
  75.     match_length = 0;
  76.     for ( ; ; ) {
  77.         if (cmp >= 0) {
  78.             if (rson[p] != NIL)
  79.                 p = rson[p];
  80.             else {
  81.                 rson[p] = r;
  82.                 dad[r] = p;
  83.                 return;
  84.             }
  85.         } else {
  86.             if (lson[p] != NIL)
  87.                 p = lson[p];
  88.             else {
  89.                 lson[p] = r;
  90.                 dad[r] = p;
  91.                 return;
  92.             }
  93.         }
  94.         for (i = 1; i < F; i++)
  95.             if ((cmp = key[i] - text_buf[p + i]) != 0)
  96.                 break;
  97.         if (i > THRESHOLD) {
  98.             if (i > match_length) {
  99.                 match_position = ((r - p) & (N - 1)) - 1;
  100.                 if ((match_length = i) >= F)
  101.                     break;
  102.             }
  103.             if (i == match_length) {
  104.                 if ((c = ((r - p) & (N - 1)) - 1) < match_position) {
  105.                     match_position = c;
  106.                 }
  107.             }
  108.         }
  109.     }
  110.     dad[r] = dad[p];
  111.     lson[r] = lson[p];
  112.     rson[r] = rson[p];
  113.     dad[lson[p]] = r;
  114.     dad[rson[p]] = r;
  115.     if (rson[dad[p]] == p)
  116.         rson[dad[p]] = r;
  117.     else
  118.         lson[dad[p]] = r;
  119.     dad[p] = NIL; /* remove p */
  120. }
  121.  
  122. static void DeleteNode(int p)  /* remove from tree */
  123. {
  124.     int  q;
  125.  
  126.     if (dad[p] == NIL)
  127.         return;         /* not registered */
  128.     if (rson[p] == NIL)
  129.         q = lson[p];
  130.     else
  131.     if (lson[p] == NIL)
  132.         q = rson[p];
  133.     else {
  134.         q = lson[p];
  135.         if (rson[q] != NIL) {
  136.             do {
  137.                 q = rson[q];
  138.             } while (rson[q] != NIL);
  139.             rson[dad[q]] = lson[q];
  140.             dad[lson[q]] = dad[q];
  141.             lson[q] = lson[p];
  142.             dad[lson[p]] = q;
  143.         }
  144.         rson[q] = rson[p];
  145.         dad[rson[p]] = q;
  146.     }
  147.     dad[q] = dad[p];
  148.     if (rson[dad[p]] == p)
  149.         rson[dad[p]] = q;
  150.     else
  151.         lson[dad[p]] = q;
  152.     dad[p] = NIL;
  153. }
  154.  
  155. /* Huffman coding */
  156.  
  157. #define N_CHAR      (256 - THRESHOLD + F)
  158.                 /* kinds of characters (character code = 0..N_CHAR-1) */
  159. #define T       (N_CHAR * 2 - 1)    /* size of table */
  160. #define R       (T - 1)         /* position of root */
  161. #define MAX_FREQ    0x8000      /* updates tree when the */
  162. typedef unsigned char uchar;
  163.  
  164.  
  165. /* table for encoding and decoding the upper 6 bits of position */
  166.  
  167. /* for encoding */
  168. uchar p_len[64] = {
  169.     0x03, 0x04, 0x04, 0x04, 0x05, 0x05, 0x05, 0x05,
  170.     0x05, 0x05, 0x05, 0x05, 0x06, 0x06, 0x06, 0x06,
  171.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  172.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  173.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  174.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  175.     0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  176.     0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08
  177. };
  178.  
  179. uchar p_code[64] = {
  180.     0x00, 0x20, 0x30, 0x40, 0x50, 0x58, 0x60, 0x68,
  181.     0x70, 0x78, 0x80, 0x88, 0x90, 0x94, 0x98, 0x9C,
  182.     0xA0, 0xA4, 0xA8, 0xAC, 0xB0, 0xB4, 0xB8, 0xBC,
  183.     0xC0, 0xC2, 0xC4, 0xC6, 0xC8, 0xCA, 0xCC, 0xCE,
  184.     0xD0, 0xD2, 0xD4, 0xD6, 0xD8, 0xDA, 0xDC, 0xDE,
  185.     0xE0, 0xE2, 0xE4, 0xE6, 0xE8, 0xEA, 0xEC, 0xEE,
  186.     0xF0, 0xF1, 0xF2, 0xF3, 0xF4, 0xF5, 0xF6, 0xF7,
  187.     0xF8, 0xF9, 0xFA, 0xFB, 0xFC, 0xFD, 0xFE, 0xFF
  188. };
  189.  
  190. /* for decoding */
  191. uchar d_code[256] = {
  192.     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  193.     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  194.     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  195.     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  196.     0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
  197.     0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
  198.     0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
  199.     0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
  200.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  201.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  202.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  203.     0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  204.     0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  205.     0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  206.     0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  207.     0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09,
  208.     0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A,
  209.     0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B,
  210.     0x0C, 0x0C, 0x0C, 0x0C, 0x0D, 0x0D, 0x0D, 0x0D,
  211.     0x0E, 0x0E, 0x0E, 0x0E, 0x0F, 0x0F, 0x0F, 0x0F,
  212.     0x10, 0x10, 0x10, 0x10, 0x11, 0x11, 0x11, 0x11,
  213.     0x12, 0x12, 0x12, 0x12, 0x13, 0x13, 0x13, 0x13,
  214.     0x14, 0x14, 0x14, 0x14, 0x15, 0x15, 0x15, 0x15,
  215.     0x16, 0x16, 0x16, 0x16, 0x17, 0x17, 0x17, 0x17,
  216.     0x18, 0x18, 0x19, 0x19, 0x1A, 0x1A, 0x1B, 0x1B,
  217.     0x1C, 0x1C, 0x1D, 0x1D, 0x1E, 0x1E, 0x1F, 0x1F,
  218.     0x20, 0x20, 0x21, 0x21, 0x22, 0x22, 0x23, 0x23,
  219.     0x24, 0x24, 0x25, 0x25, 0x26, 0x26, 0x27, 0x27,
  220.     0x28, 0x28, 0x29, 0x29, 0x2A, 0x2A, 0x2B, 0x2B,
  221.     0x2C, 0x2C, 0x2D, 0x2D, 0x2E, 0x2E, 0x2F, 0x2F,
  222.     0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37,
  223.     0x38, 0x39, 0x3A, 0x3B, 0x3C, 0x3D, 0x3E, 0x3F,
  224. };
  225.  
  226. uchar d_len[256] = {
  227.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  228.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  229.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  230.     0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
  231.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  232.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  233.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  234.     0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  235.     0x04, 0x04, 0x04, 0x04,